package arithmetic.LeetCode;

import java.util.Arrays;

import org.junit.jupiter.api.Test;

/**
 * 239. 滑动窗口最大值
 * <p>
 * 给你一个整数数组 nums，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * <p>
 * 返回 滑动窗口中的最大值 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sliding-window-maximum
 *
 * @author jiangfeng on 2023/4/7
 */
public class SlidingWindowMax {

    @Test
    public void test() {
        //System.out.println(Arrays.toString(maxSlidingWindow(new int[] {1,3,-1,-3,5,3,6,7}, 3)));
        // 挤出去了,却比尾巴大.
        //System.out.println(Arrays.toString(maxSlidingWindow(new int[] {7,2,4}, 2)));

        // 输出：   [3,3,1,5]
        // 预期结果：[3,3,2,5]
        // 原因:入队的时候,如果比队头小但是比队尾大,应该把队尾小的都干掉,维持队列从头到小的单调性
        // 进元素,
        //System.out.println(Arrays.toString(maxSlidingWindow(new int[] {1, 3, 1, 2, 0, 5}, 3)));

        // 输出:[7, 7, 7, 6, 6]
        // 预期:[7, 7, 7, 7, 7]
        // 相同头部元素应该让进
        //System.out.println(Arrays.toString(maxSlidingWindow(new int[] {-7,-8,7,5,7,1,6,0}, 4)));

        //
        System.out.println(Arrays.toString(maxSlidingWindow(new int[] {10,9,8,7,5,4,3,2,1,0,-1,-2,-3,-5,-6,-7,-8,-9,-10}, 4)));

    }

    //使用单调队列.
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 1) {
            return nums;
        }
        // 单调队列.
        MonoQueen mnq = new MonoQueen(k);
        int[] result = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            // 滑动窗口入
            mnq.push(nums[i]);

            if (i >= k - 1) {
                if (i >= k) {
                    // 滑动窗口出
                    mnq.pop(nums[i - k]);
                }
                // 第k个开始计算结果
                result[i - k + 1] = mnq.getHead();
            }
        }
        return result;
    }

    class MonoQueen {
        // 用循环数组来实现队列:维护队头的下标
        int[] queen;
        int start;
        int end;
        boolean init;

        public MonoQueen(int size) {
            start = 0;
            end = 0;
            init = false;
            // 因为是数组实现的循环队列,所以多给个元素空间位置,防止中间判断的时候给覆盖了,
            queen = new int[size+1];
        }

        public int getHead() {
            if (!init) {
                throw new IllegalStateException();
            }
            return this.queen[this.start];
        }


        // 出, 如果出的元素就是队头元素才出.
        public void pop(int i) {
            if (getHead() == i) {
                this.start++;
                // 循环队列处理
                if (this.start == this.queen.length) {
                    this.start = 0;
                }
            }
        }

        // 进
        public void push(int i) {
            //标识第一次
            if (!init) {
                this.queen[this.end++] = i;
                init = true;
                return;
            }

            // 元素比对头还大:直接清空数组并放入头
            if (i > getHead()) {
                this.end = 0;
                this.start = 0;
                this.queen[this.end++] = i;
            }

            // 元素比队头小,入队操作
            else {
                // 在看看比队尾小么?
                while (i > this.getBack() ) {
                    this.popBack();
                }

                this.queen[this.end] = i;
                //循环队列处理
                this.end++;
                if (this.end == this.queen.length) {
                    this.end = 0;
                }
            }

        }

        private int getBack() {
            if (!init) {
                throw new IllegalStateException();
            }
            // 循环队列处理
            return this.end == 0 ? this.queen[this.queen.length - 1] : this.queen[this.end - 1];
        }

        // 去队尾
        private void popBack() {
            this.end = this.end == 0 ? this.queen.length - 1 : this.end - 1;
        }
    }

}
